Global strategies
Some algorithms have been developed as attempts to find the global
minimum of a smooth target function. We discuss two here: stochastic
local search and simulated annealing. There two algorithms provide no
absolute guarantee for finding the global minimum, but are less likely
to get stuck in the local minima.
Stochastic Local Search
Recall the basic gradient descent \[
w_{t+1} \leftarrow w_t -\alpha_t \nabla L(w_t), \quad \alpha_t>0.
\] The general idea for stochastic gradient descent (local
search) is that we move \(w_t\) to
\(w_{t+1}\) in a random direction, say
\(w_{t+1} \leftarrow w_t +
\epsilon_t\), for some random \(\epsilon_t\). Consider the
finite-difference approximation \[
\tilde{\nabla} L(w_t) = \frac{L(w_t+\beta_t \eta_t)- L(w_t-\beta_t
\eta_t)}{2 \beta_t} \eta_t:=\frac{\Delta L(w_t, \beta_t
\eta_t)}{2\beta_t}\eta_t,
\]
We set \(\{\beta_t\}\) decreasing to
\(0\). Note that \(\lim_{\beta_t\to0} (\Delta L(w_t, \beta_t
\eta_t)/2\beta_t)=\nabla_{\eta_t}L(w_t)=\left\langle\nabla
L(w_t),\eta_t\right\rangle\) the directional derivative of \(L\) along the direction \(\eta_t,\) for example,
- \(\eta_t\) uniformly distributed
over the unit sphere \(\|\eta\|=1\),
say on \(\mathbb{R}^2\), take \(w_1 \sim N(0,1), w_2\sim N(0,1)\) and
define \(\eta_1=w_1/\sqrt{w_1^2+w_2^2},
\eta_2=w_2/\sqrt{w_1^2+w_2^2}.\)
The update is \[
w_{t+1} \leftarrow w_t-\alpha_t \tilde{\nabla} L(w_t).
\]
When the value of \(\beta_t\) is
large, the process doesn’t follow the steepest descent in \(w_t\) but instead takes a more random path.
This random exploration in the early phases helps avoiding getting
trapped in some potential local minima. As time goes on, the update
direction satisfies descent direction almost certainly but it is still
randomly perturbed. It is crucial to have some step length \(\alpha_t\) to moderate the descent.
The choice of \(\alpha_t,
\beta_t\):
- \(\alpha_t\) decreases slowly to
\(0\); \(\beta_t\) decreases more slowly than \(\alpha_t\)
- \(\sum_{t} \alpha_t =\infty\)
- \(\sum_{t}(\alpha_t/\beta_t)^2
<\infty\), e.g., \(\alpha_t=1/(t+1)\), \(\beta_t=1/(t+1)^{0.1}\)
Simulated Annealing
In metallurgy, annealing refers to the process where a solid is
heated to release its thermal stresses, and then cooled slowly to allow
its crystals to arrange in a configuration that minimizes energy. The
quality of the end result, i.e., the arrangement of the crystals, is
dependent on the rate of cooling. Faster cooling may trap the material
in a sub-optimal configuration, whereas slow cooling is more likely to
result in a configuration closer to the global minimum energy state.
Consider maximize \(h(\theta)\)
(global maximization):
Assume \(h: \Theta \mapsto \mathbb{R},
\int_H h(\theta)<\infty\).
Define the so-called Boltzman-Gibbs transformation of \(h\) to be \[\pi_t(\theta) = exp
\Big(\frac{h(\theta)}{T_t}\Big),\] where \(T_t>0\) is the temperature at time \(t\).
One can treat \(\pi_t(\theta)\) as
some unnormalized version (i.e., the kernel) for the density function of
\(\theta\).
As \(T_t \downarrow\) 0, the kernel
of density will become more and more concentrated in a narrower
neighborhood of the maximizer of \(h\).
example: The following is the plot of \(\exp \left(\frac{h(\theta)}{T_t}\right)\),
where \(h\) is two dimensional
Rastrigin function: \(-(2A+\sum_{i=1}^2\left[x_i^2-A \cos \left(2 \pi
x_i\right)\right])\) where \(A=10\) and \(x_i
\in[-5.12,5.12]\):

Algorithm (Metropolis-Hastings):
Suppose \(g(\cdot)\) symmetric
density function \(g(-x)=g(x)\),
e.g. \(N(0,1)\).
simulate \(\zeta^{(t)}\) from
\(g\).
generate \(\theta^{(t+1)}\) as
\[\theta^{(t+1)}=
\begin{cases}
\theta^{(t)}+\zeta^{(t)} & \text{with } \ prob\
\rho=\min\{exp(\frac{\triangle h}{T_t}), 1\}, \triangle h =
h(\theta^{(t)}+\zeta^{(t)})-h(\theta^{(t)})\\
\theta^{(t)} & \text{with }\ prob \ 1-\rho\\
\end{cases}.\]
reduce temperature \(T_{t+1} \leftarrow
T_t\). For example, one can let \(T_t =
1/log(1+t)\) or \((1/1.2)^t.\)
Remarks:
If the perturbation increases \(h\) (i.e., \(\triangle h\geq 0\)), the new proposal is
automatically accepted. If \(\triangle
h<0\), then still accept it with certain probability \(\rho(<1)\).
When \(T_t\) is relatively
large, many “bad” proposals (that is those \(\triangle h<0\)) may still be accepted.
Therefore a larger part of the space can be explored. As \(T_t \downarrow 0\), that will limit the
“bad” proposal that we allow.
When \(T_t\) is sufficiently
small, one essentially “anneal” the process by accepting only “good”
proposals (i.e., \(\triangle h\geq
0\)).
In step 2, one can instead sample \(u\sim unif(0, 1)\), and if \(u \leq \exp(\Delta h/T_t)\), we set \(\theta^{(t+1)} \leftarrow \theta^{(t)} +
\zeta^{(t)},\) otherwise, we \(\theta^{(t+1)} \leftarrow
\theta^{(t)}.\)
If \(T_t\) is fixed, the
algorithm essentially draws a Markov Chain whose stationary distribution
ig given by \(\theta \propto
\exp(h(\theta)/T)\).
The following is the plot of the function \(\rho\left(T_t\right)\) against \(T_t\), with \(T_t\) decreasing from 10 to 0.1 and \(\Delta h=-0.1\):

Python Code Examples
Provided and discussed in lab.
Back
Updated: 2023-12-08
Statistical Simulation, Wei Li
LS0tCnRpdGxlOiAiTUFUIDY1MzogU3RhdGlzdGljYWwgU2ltdWxhdGlvbiIKYXV0aG9yOiBJbnN0cnVjdG9yJDokIERyLiBXZWkgTGkKZGF0ZTogImByIFN5cy5EYXRlKClgIgpnZW9tZXRyeTogbGVmdD0yY20sIHJpZ2h0PTJjbSwgdG9wPTJjbSwgYm90dG9tPTJjbQpsaW5lc3RyZXRjaDogMS4zCm91dHB1dDoKICBodG1sX2RvY3VtZW50OgogICAgZGZfcHJpbnQ6IHBhZ2VkCiAgICBtYXRoamF4X2NvbmZpZzoKICAgICAgLSBUZVgtQU1TLU1NTF9IVE1Mb3JNTUwgICAKICBwZGZfZG9jdW1lbnQ6IAogICAgICBpbmNsdWRlOgogICAgICAgIGluX2hlYWRlcjogcHJlYW1ibGVfcm1kLnRleAogIGh0bWxfbm90ZWJvb2s6IGRlZmF1bHQKZm9udHNpemU6IDE0cHQKaGVhZGVyLWluY2x1ZGVzOgotIFx1c2VwYWNrYWdle2Ftc21hdGh9Ci0gXHVzZXBhY2thZ2VbbGluZXdpZHRoPTFwdF17bWRmcmFtZWR9Ci0gXG5ld2NvbW1hbmRcaW5uZXJbMl17XGxlZnRcbGFuZ2xlIzEsIzJccmlnaHRccmFuZ2xlfQotIFxuZXdjb21tYW5kXGZsb29yWzFde1xsZmxvb3IjMVxyZmxvb3J9Ci0gXG5ld2NvbW1hbmRcY2VpbFsxXXtcbGNlaWwjMVxyY2VpbH0KLSBcbmV3Y29tbWFuZFxtYlsxXXtcbWF0aGJmeyMxfX0KLSBcbmV3Y29tbWFuZFxic1sxXXtcYm9sZHN5bWJvbHsjMX19Ci0gXG5ld2NvbW1hbmRcbXJbMV17XG1hdGhybXsjMX19Ci0gXG5ld2NvbW1hbmRcd2hbMV17XHdpZGVoYXR7IzF9fQotIFxuZXdjb21tYW5kXG9wWzFde1xvcGVyYXRvcm5hbWV7IzF9fQotIFxuZXdjb21tYW5kXG1iYlsxXXtcbWF0aGJieyMxfX0KLSBcbmV3Y29tbWFuZFxUe1x0b3B9Ci0gXG5ld2NvbW1hbmR7XHdlaX1bMV17XHRleHRjb2xvcntvcmFuZ2V9eyhXZWk6IzEpfX0KLSBcdXNlcGFja2FnZXttYXRodG9vbHN9Ci0gXHVzZXBhY2thZ2V7Y2FwdGlvbn0KLSBcY2FwdGlvbnNldHVwW2ZpZ3VyZV17bGFiZWxmb3JtYXQ9ZW1wdHl9Ci0tLQoKCjxzY3JpcHQgdHlwZT0idGV4dC94LW1hdGhqYXgtY29uZmlnIj4KTWF0aEpheC5IdWIuQ29uZmlnKHsKICBUZVg6IHsgZXF1YXRpb25OdW1iZXJzOiB7IGF1dG9OdW1iZXI6ICJBTVMiIH0gfQp9KTsKPC9zY3JpcHQ+CgoKPHNwYW4gc3R5bGU9ImJhY2tncm91bmQtY29sb3I6ICNmNWY1ZjU7IHBhZGRpbmc6IDVweDsgZGlzcGxheTogYmxvY2s7Ij4KICAgIDxzcGFuIHN0eWxlPSJ3aWR0aDogMjUlOyBkaXNwbGF5OiBpbmxpbmUtYmxvY2s7IHRleHQtYWxpZ246IGxlZnQ7Ij4KICAgICAgICBbQmFja10oamF2YXNjcmlwdDp3aW5kb3cuaGlzdG9yeS5iYWNrKCkpCiAgICA8L3NwYW4+CiAgICA8c3BhbiBzdHlsZT0id2lkdGg6IDMwJTsgZGlzcGxheTogaW5saW5lLWJsb2NrOyB0ZXh0LWFsaWduOiBjZW50ZXI7IGNvbG9yOiBncmV5OyI+CiAgICAgICAgKipVcGRhdGVkOioqIGByIFN5cy5EYXRlKClgCiAgICA8L3NwYW4+CiAgICA8c3BhbiBzdHlsZT0id2lkdGg6IDM1JTsgZGlzcGxheTogaW5saW5lLWJsb2NrOyB0ZXh0LWFsaWduOiByaWdodDsgY29sb3I6IGdyZXk7Ij4KICAgICAgICBTdGF0aXN0aWNhbCBTaW11bGF0aW9uLCBXZWkgTGkKICAgIDwvc3Bhbj4KPC9zcGFuPgoKPCEtLS0tLS0tLS0tLS0tPgoKIyBHbG9iYWwgc3RyYXRlZ2llcwoKU29tZSBhbGdvcml0aG1zIGhhdmUgYmVlbiBkZXZlbG9wZWQgYXMgYXR0ZW1wdHMgdG8gZmluZCB0aGUgZ2xvYmFsIG1pbmltdW0gb2YgYSBzbW9vdGggdGFyZ2V0IGZ1bmN0aW9uLiBXZSBkaXNjdXNzIHR3byBoZXJlOiBzdG9jaGFzdGljIGxvY2FsIHNlYXJjaCBhbmQgc2ltdWxhdGVkIGFubmVhbGluZy4gVGhlcmUgdHdvIGFsZ29yaXRobXMgcHJvdmlkZSBubyBhYnNvbHV0ZSBndWFyYW50ZWUgZm9yIGZpbmRpbmcgdGhlIGdsb2JhbCBtaW5pbXVtLCBidXQgYXJlIGxlc3MgbGlrZWx5IHRvIGdldCBzdHVjayBpbiB0aGUgbG9jYWwgbWluaW1hLgoKIyMjIFN0b2NoYXN0aWMgTG9jYWwgU2VhcmNoCgpSZWNhbGwgdGhlIGJhc2ljIGdyYWRpZW50IGRlc2NlbnQKJCQKd197dCsxfSBcbGVmdGFycm93IHdfdCAtXGFscGhhX3QgXG5hYmxhIEwod190KSwgXHF1YWQgXGFscGhhX3Q+MC4KJCQKVGhlIGdlbmVyYWwgaWRlYSBmb3Igc3RvY2hhc3RpYyBncmFkaWVudCBkZXNjZW50IChsb2NhbCBzZWFyY2gpIGlzIHRoYXQgd2UgbW92ZSAkd190JCB0byAkd197dCsxfSQgaW4gYSByYW5kb20gZGlyZWN0aW9uLCBzYXkgJHdfe3QrMX0gXGxlZnRhcnJvdyB3X3QgKyBcZXBzaWxvbl90JCwgZm9yIHNvbWUgcmFuZG9tICRcZXBzaWxvbl90JC4gQ29uc2lkZXIgdGhlIGZpbml0ZS1kaWZmZXJlbmNlIGFwcHJveGltYXRpb24KJCQKXHRpbGRle1xuYWJsYX0gTCh3X3QpID0gXGZyYWN7TCh3X3QrXGJldGFfdCBcZXRhX3QpLSBMKHdfdC1cYmV0YV90IFxldGFfdCl9ezIgXGJldGFfdH0gXGV0YV90Oj1cZnJhY3tcRGVsdGEgTCh3X3QsIFxiZXRhX3QgXGV0YV90KX17MlxiZXRhX3R9XGV0YV90LAokJAoKV2Ugc2V0ICRce1xiZXRhX3RcfSQgZGVjcmVhc2luZyB0byAkMCQuIE5vdGUgdGhhdCAkXGxpbV97XGJldGFfdFx0bzB9IChcRGVsdGEgTCh3X3QsIFxiZXRhX3QgXGV0YV90KS8yXGJldGFfdCk9XG5hYmxhX3tcZXRhX3R9TCh3X3QpPVxpbm5lcntcbmFibGEgTCh3X3QpfXtcZXRhX3R9JCB0aGUgZGlyZWN0aW9uYWwgZGVyaXZhdGl2ZSBvZiAkTCQgYWxvbmcgdGhlIGRpcmVjdGlvbiAkXGV0YV90LCQgZm9yIGV4YW1wbGUsCgotICRcZXRhX3QkIHVuaWZvcm1seSBkaXN0cmlidXRlZCBvdmVyIHRoZSB1bml0IHNwaGVyZSAkXHxcZXRhXHw9MSQsIHNheSBvbiAkXG1hdGhiYntSfV4yJCwgdGFrZSAkd18xIFxzaW0gTigwLDEpLCB3XzJcc2ltIE4oMCwxKSQgYW5kIGRlZmluZSAkXGV0YV8xPXdfMS9cc3FydHt3XzFeMit3XzJeMn0sIFxldGFfMj13XzIvXHNxcnR7d18xXjIrd18yXjJ9LiQKClRoZSB1cGRhdGUgaXMgCiQkCndfe3QrMX0gXGxlZnRhcnJvdyB3X3QtXGFscGhhX3QgXHRpbGRle1xuYWJsYX0gTCh3X3QpLgokJAoKV2hlbiB0aGUgdmFsdWUgb2YgJFxiZXRhX3QkIGlzIGxhcmdlLCB0aGUgcHJvY2VzcyBkb2Vzbid0IGZvbGxvdyB0aGUgc3RlZXBlc3QgZGVzY2VudCBpbiAkd190JCBidXQgaW5zdGVhZCB0YWtlcyBhIG1vcmUgcmFuZG9tIHBhdGguIFRoaXMgcmFuZG9tIGV4cGxvcmF0aW9uIGluIHRoZSBlYXJseSBwaGFzZXMgaGVscHMgYXZvaWRpbmcgZ2V0dGluZyB0cmFwcGVkIGluIHNvbWUgcG90ZW50aWFsIGxvY2FsIG1pbmltYS4gQXMgdGltZSBnb2VzIG9uLCB0aGUgdXBkYXRlIGRpcmVjdGlvbiBzYXRpc2ZpZXMgZGVzY2VudCBkaXJlY3Rpb24gYWxtb3N0IGNlcnRhaW5seSBidXQgaXQgaXMgc3RpbGwgcmFuZG9tbHkgcGVydHVyYmVkLiBJdCBpcyBjcnVjaWFsIHRvIGhhdmUgc29tZSBzdGVwIGxlbmd0aCAkXGFscGhhX3QkIHRvIG1vZGVyYXRlIHRoZSBkZXNjZW50LgoKVGhlIGNob2ljZSBvZiAkXGFscGhhX3QsIFxiZXRhX3QkOgoKLSAkXGFscGhhX3QkIGRlY3JlYXNlcyBzbG93bHkgdG8gJDAkOyAkXGJldGFfdCQgZGVjcmVhc2VzIG1vcmUgc2xvd2x5IHRoYW4gJFxhbHBoYV90JAotICRcc3VtX3t0fSBcYWxwaGFfdCA9XGluZnR5JAotICRcc3VtX3t0fShcYWxwaGFfdC9cYmV0YV90KV4yIDxcaW5mdHkkLCBlLmcuLCAkXGFscGhhX3Q9MS8odCsxKSQsICRcYmV0YV90PTEvKHQrMSleezAuMX0kCgojIyMgU2ltdWxhdGVkIEFubmVhbGluZwoKSW4gbWV0YWxsdXJneSwgYW5uZWFsaW5nIHJlZmVycyB0byB0aGUgcHJvY2VzcyB3aGVyZSBhIHNvbGlkIGlzIGhlYXRlZCB0byByZWxlYXNlIGl0cyB0aGVybWFsIHN0cmVzc2VzLCBhbmQgdGhlbiBjb29sZWQgc2xvd2x5IHRvIGFsbG93IGl0cyBjcnlzdGFscyB0byBhcnJhbmdlIGluIGEgY29uZmlndXJhdGlvbiB0aGF0IG1pbmltaXplcyBlbmVyZ3kuIFRoZSBxdWFsaXR5IG9mIHRoZSBlbmQgcmVzdWx0LCBpLmUuLCB0aGUgYXJyYW5nZW1lbnQgb2YgdGhlIGNyeXN0YWxzLCBpcyBkZXBlbmRlbnQgb24gdGhlIHJhdGUgb2YgY29vbGluZy4gRmFzdGVyIGNvb2xpbmcgbWF5IHRyYXAgdGhlIG1hdGVyaWFsIGluIGEgc3ViLW9wdGltYWwgY29uZmlndXJhdGlvbiwgd2hlcmVhcyBzbG93IGNvb2xpbmcgaXMgbW9yZSBsaWtlbHkgdG8gcmVzdWx0IGluIGEgY29uZmlndXJhdGlvbiBjbG9zZXIgdG8gdGhlIGdsb2JhbCBtaW5pbXVtIGVuZXJneSBzdGF0ZS4KCkNvbnNpZGVyIG1heGltaXplICRoKFx0aGV0YSkkIChnbG9iYWwgbWF4aW1pemF0aW9uKToKCkFzc3VtZSAkaDogXFRoZXRhIFxtYXBzdG8gXG1hdGhiYntSfSwgXGludF9IIGgoXHRoZXRhKTxcaW5mdHkkLgoKRGVmaW5lIHRoZSBzby1jYWxsZWQgQm9sdHptYW4tR2liYnMgdHJhbnNmb3JtYXRpb24gb2YgJGgkIHRvIGJlIAokJFxwaV90KFx0aGV0YSkgPSBleHAgXEJpZyhcZnJhY3toKFx0aGV0YSl9e1RfdH1cQmlnKSwkJCAKd2hlcmUgJFRfdD4wJCBpcyB0aGUgdGVtcGVyYXR1cmUgYXQgdGltZSAkdCQuCgpPbmUgY2FuIHRyZWF0ICRccGlfdChcdGhldGEpJCBhcyBzb21lIHVubm9ybWFsaXplZCB2ZXJzaW9uIChpLmUuLCB0aGUga2VybmVsKSBmb3IgdGhlIGRlbnNpdHkgZnVuY3Rpb24gb2YgJFx0aGV0YSQuCgpBcyAkVF90IFxkb3duYXJyb3ckIDAsIHRoZSBrZXJuZWwgb2YgZGVuc2l0eSB3aWxsIGJlY29tZSBtb3JlIGFuZCBtb3JlIGNvbmNlbnRyYXRlZCBpbiBhIG5hcnJvd2VyIG5laWdoYm9yaG9vZCBvZiB0aGUgbWF4aW1pemVyIG9mICRoJC4KCioqZXhhbXBsZSoqOiBUaGUgZm9sbG93aW5nIGlzIHRoZSBwbG90IG9mICRcZXhwIFxsZWZ0KFxmcmFje2goXHRoZXRhKX17VF90fVxyaWdodCkkLCB3aGVyZSAkaCQgaXMgdHdvIGRpbWVuc2lvbmFsIFJhc3RyaWdpbiBmdW5jdGlvbjogJC0oMkErXHN1bV97aT0xfV4yXGxlZnRbeF9pXjItQSBcY29zIFxsZWZ0KDIgXHBpIHhfaVxyaWdodClccmlnaHRdKSQgd2hlcmUgJEE9MTAkIGFuZCAkeF9pIFxpblstNS4xMiw1LjEyXSQ6CgohW10oLi4vaW1hZ2VzL3NpbXVsYXRlZF9hbm5lYWxpbmcxLnBuZyl7IHdpZHRoPTYwJSB9CgoqKkFsZ29yaXRobSAoTWV0cm9wb2xpcy1IYXN0aW5ncykqKjoKClN1cHBvc2UgJGcoXGNkb3QpJCBzeW1tZXRyaWMgZGVuc2l0eSBmdW5jdGlvbiAkZygteCk9Zyh4KSQsIGUuZy4gJE4oMCwxKSQuCgoxLiBzaW11bGF0ZSAkXHpldGFeeyh0KX0kIGZyb20gJGckLgoKMi4gZ2VuZXJhdGUgJFx0aGV0YV57KHQrMSl9JCBhcwokJFx0aGV0YV57KHQrMSl9PQpcYmVnaW57Y2FzZXN9Clx0aGV0YV57KHQpfStcemV0YV57KHQpfSAmIFx0ZXh0e3dpdGggfSBcIHByb2JcIFxyaG89XG1pblx7ZXhwKFxmcmFje1x0cmlhbmdsZSBofXtUX3R9KSwgMVx9LCBcdHJpYW5nbGUgaCA9IGgoXHRoZXRhXnsodCl9K1x6ZXRhXnsodCl9KS1oKFx0aGV0YV57KHQpfSlcXApcdGhldGFeeyh0KX0gJiBcdGV4dHt3aXRoIH1cIHByb2IgXCAxLVxyaG9cXApcZW5ke2Nhc2VzfS4kJAoKMy4gcmVkdWNlIHRlbXBlcmF0dXJlICRUX3t0KzF9IFxsZWZ0YXJyb3cgVF90JC4gRm9yIGV4YW1wbGUsIG9uZSBjYW4gbGV0ICRUX3QgPSAxL2xvZygxK3QpJCBvciAkKDEvMS4yKV50LiQKCioqUmVtYXJrcyoqOgoKMS4gSWYgdGhlIHBlcnR1cmJhdGlvbiBpbmNyZWFzZXMgJGgkIChpLmUuLCAkXHRyaWFuZ2xlIGhcZ2VxIDAkKSwgdGhlIG5ldyBwcm9wb3NhbCBpcyBhdXRvbWF0aWNhbGx5IGFjY2VwdGVkLiBJZiAkXHRyaWFuZ2xlIGg8MCQsIHRoZW4gc3RpbGwgYWNjZXB0IGl0IHdpdGggY2VydGFpbiBwcm9iYWJpbGl0eSAgJFxyaG8oPDEpJC4KCjIuIFdoZW4gJFRfdCQgaXMgcmVsYXRpdmVseSBsYXJnZSwgbWFueSAiYmFkIiBwcm9wb3NhbHMgKHRoYXQgaXMgdGhvc2UgJFx0cmlhbmdsZSBoPDAkKSBtYXkgc3RpbGwgYmUgYWNjZXB0ZWQuIFRoZXJlZm9yZSBhIGxhcmdlciBwYXJ0IG9mIHRoZSBzcGFjZSBjYW4gYmUgZXhwbG9yZWQuIEFzICRUX3QgXGRvd25hcnJvdyAwJCwgdGhhdCB3aWxsIGxpbWl0IHRoZSAiYmFkIiBwcm9wb3NhbCB0aGF0IHdlIGFsbG93LgoKMy4gV2hlbiAkVF90JCBpcyBzdWZmaWNpZW50bHkgc21hbGwsIG9uZSBlc3NlbnRpYWxseSAiYW5uZWFsIiB0aGUgcHJvY2VzcyBieSBhY2NlcHRpbmcgb25seSAiZ29vZCIgcHJvcG9zYWxzIChpLmUuLCAkXHRyaWFuZ2xlIGhcZ2VxIDAkKS4KCjQuIEluIHN0ZXAgMiwgb25lIGNhbiBpbnN0ZWFkIHNhbXBsZSAkdVxzaW0gdW5pZigwLCAxKSQsIGFuZCBpZiAkdSBcbGVxIFxleHAoXERlbHRhIGgvVF90KSQsIHdlIHNldCAkXHRoZXRhXnsodCsxKX0gXGxlZnRhcnJvdyBcdGhldGFeeyh0KX0gKyBcemV0YV57KHQpfSwkIG90aGVyd2lzZSwgd2UgJFx0aGV0YV57KHQrMSl9IFxsZWZ0YXJyb3cgXHRoZXRhXnsodCl9LiQKCjUuIElmICRUX3QkIGlzIGZpeGVkLCB0aGUgYWxnb3JpdGhtIGVzc2VudGlhbGx5IGRyYXdzIGEgTWFya292IENoYWluIHdob3NlIHN0YXRpb25hcnkgZGlzdHJpYnV0aW9uIGlnIGdpdmVuIGJ5ICRcdGhldGEgXHByb3B0byBcZXhwKGgoXHRoZXRhKS9UKSQuCgpUaGUgZm9sbG93aW5nIGlzIHRoZSBwbG90IG9mIHRoZSBmdW5jdGlvbiAkXHJob1xsZWZ0KFRfdFxyaWdodCkkIGFnYWluc3QgJFRfdCQsIHdpdGggJFRfdCQgZGVjcmVhc2luZyBmcm9tIDEwIHRvIDAuMSBhbmQgJFxEZWx0YSBoPS0wLjEkOgoKIVtdKC4uL2ltYWdlcy9zaW11bGF0ZWRfYW5uZWFsaW5nMi5wbmcpeyB3aWR0aD02MCUgfQoKIyMjIFB5dGhvbiBDb2RlIEV4YW1wbGVzCgpQcm92aWRlZCBhbmQgZGlzY3Vzc2VkIGluIGxhYi4KCgo8IS0tLS0tLS0tLS0tLS0+CjxzcGFuIHN0eWxlPSJiYWNrZ3JvdW5kLWNvbG9yOiAjZjVmNWY1OyBwYWRkaW5nOiA1cHg7IGRpc3BsYXk6IGJsb2NrOyI+CiAgICA8c3BhbiBzdHlsZT0id2lkdGg6IDI1JTsgZGlzcGxheTogaW5saW5lLWJsb2NrOyB0ZXh0LWFsaWduOiBsZWZ0OyI+CiAgICAgICAgW0JhY2tdKGphdmFzY3JpcHQ6d2luZG93Lmhpc3RvcnkuYmFjaygpKQogICAgPC9zcGFuPgogICAgPHNwYW4gc3R5bGU9IndpZHRoOiAzMCU7IGRpc3BsYXk6IGlubGluZS1ibG9jazsgdGV4dC1hbGlnbjogY2VudGVyOyBjb2xvcjogZ3JleTsiPgogICAgICAgICoqVXBkYXRlZDoqKiBgciBTeXMuRGF0ZSgpYAogICAgPC9zcGFuPgogICAgPHNwYW4gc3R5bGU9IndpZHRoOiAzNSU7IGRpc3BsYXk6IGlubGluZS1ibG9jazsgdGV4dC1hbGlnbjogcmlnaHQ7IGNvbG9yOiBncmV5OyI+CiAgICAgICAgU3RhdGlzdGljYWwgU2ltdWxhdGlvbiwgV2VpIExpCiAgICA8L3NwYW4+Cjwvc3Bhbj4=